package com.success.toutiao;

import org.junit.Test;

/**
 * Desc: 2018.11.28
 * 头条面试，提供笔记本，编程3选1，第一题
 * leetcode:https://leetcode.com/problems/word-search/
 * Create by John Jiang On 2018/12/19
 */
public class WordSerarch {
    public boolean exist(char[][] board, String word) {
        int n = board.length;
        int m = board[0].length;
        boolean[][] access = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                access[i][j] = true;
            }
        }
        boolean flag = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                flag = search(board, word.toCharArray(), 0, i, j, access);
                if (flag) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean search(char[][] board, char[] chars, int index, int i, int j, boolean[][] access) {
        if (index >= chars.length) {
            return true;
        }
        if (chars[index] != board[i][j]) {
            return false;
        }
        if (index == chars.length - 1) {
            return true;
        }
        boolean flag = false;
        access[i][j] = false;
        if (i > 0 && access[i - 1][j]) {
            flag = search(board, chars, index + 1, i - 1, j, access);
        }
        if (flag) {
            return true;
        }
        if (i < board.length - 1 && access[i + 1][j]) {
            flag = search(board, chars, index + 1, i + 1, j, access);
        }
        if (flag) {
            access[i][j] = true;
            return true;
        }
        if (j > 0 && access[i][j - 1]) {
            flag = search(board, chars, index + 1, i, j - 1, access);
        }
        if (flag) {
            access[i][j] = true;
            return true;
        }
        if (j < board[i].length - 1 && access[i][j + 1]) {
            flag = search(board, chars, index + 1, i, j + 1, access);
        }
        if (flag) {
            access[i][j] = true;
            return true;
        }
        access[i][j] = true;
        return false;
    }

    @Test
    public void test() {
        char[][] broad = {{'a', 'b'}};
        String test = "ba";
        System.out.println(exist(broad, test));
    }
}
